1. Field of the Invention
The present invention relates to a method and apparatus for reducing the frequency of collisions in a hashed content addressable memory (CAM) array.
2. Related Art
A hashing function irreversibly reduces a relatively wide data value to a relatively narrow data value. Advantageously, the narrow data value can then be processed more easily than the wide data value. For example, the narrow data value can be used to access information associated with the wide data value. However, the nature of a hashing function can result in collisions. A collision occurs when two different wide data values are hashed down to the same narrow data value. To resolve collisions, a system must store the wide data values, and determine when two of the wide data values hash to the same narrow data value. Upon detecting a collision, the system must then have a process for resolving the collision. In one process, the wide data values are stored, and subsequently searched during a collision. One conventional search method is to search data organized in a binary tree in a serial manner. However, such a search method is relatively slow. Another conventional search method is to search using a content addressable memory (CAM) array. However, CAM arrays typically have a relatively small width, and are unable to accommodate searches of wide data values in an efficient manner. Organizing, storing and searching these wide data values is time consuming when performed by a system processor.
FIG. 1 is a block diagram of a conventional system 100 used to process wide data values. System 100 includes hashing function 101, multiplexer 102, registers 103-105, comparator 107 and random access memory (RAM) routing table 110. Hashing function 101 is configured to receive a relatively wide (e.g., 256-bit) data value, KEY. Hash function 101 provides a relatively narrow (e.g., 20-bit) hashed value (H_VALUE) in response to the KEY value. As described above, it is possible for hashing function 101 to provide the same H_VALUE in response to different KEY values. In the present example, the KEY values “ZZZ”, “YYZ” and “ABC” all hash to the same H_VALUE, “AA”.
The KEY values “ZZZ”, “YYZ” and “ABC” are stored in RAM 110 in a chained manner. Thus, KEY value “ZZZ”, which is selected as the first value in the chain, is stored at address location “AA” of RAM 110. Also stored in address location “AA” are: (1) the address of the next KEY value in the chain (i.e., address “BB”), and (2) information (i.e., “MMM”), such as routing data, associated with the KEY value “ZZZ”.
The KEY value “YYZ”, which is selected as the second value in the chain, is stored at address location “BB” of RAM 110. Also stored in address location “BB” are:
(1) the address of the next KEY value in the chain (i.e., “CC”) and (2) information (i.e., “NNN”) associated with the KEY value “YYZ”.
The KEY value “ABC”, which is the last value in the chain, is stored at address location “CC” of RAM 110. Also stored in address location “CC” is the information (i.e., “PPP”) associated with the KEY value “ABC”.
System 100 operates as follows. Hashing function 101 provides an H_VALUE of “AA” when a KEY value of “ABC” is provided to hashing function 101. Multiplexer 102 is configured to provide this H_VALUE to register 103. Register 103 stores this H_VALUE, which is provided to RAM 110 as an address value (ADDR). In response, RAM 110 accesses the entry stored at address “AA”. Thus, the next address value associated with this entry (i.e., “BB”) is loaded into register 104, and the key value associated with this entry (i.e., “ZZZ”) is loaded into register 105. Comparator 107 compares the contents of register 105 (“ZZZ”) with the original KEY value (“ABC”) and determines that there is no match (i.e., HIT=0). In response, multiplexer 102 is configured to route the address value “BB” stored in register 104.
This address value “BB” is loaded into register 103, and provided to RAM 110. In response, RAM 110 accesses the entry stored at address “BB”. The next address value associated with this entry (i.e., “CC”) is loaded into register 104, and the key value associated with this entry (i.e., “YYZ”) is loaded into register 105. Comparator 107 then compares the contents of register 105 (“YYZ”) with the original KEY value (“ABC”) and determines that there is no match. In response, multiplexer 102 is configured to route the next address value “CC” stored in register 104.
This address value “CC” is loaded into register 103, and provided to RAM 110. In response, RAM 110 accesses the entry stored at address “CC”. The next address value associated with this entry (i.e., “--”) is loaded into register 104, and the key value associated with this entry (i.e., “ABC”) is loaded into register 105.
Comparator 107 compares the contents of register 105 (“ABC”) with the original KEY value (“ABC”) and determines that a match exists (i.e., HIT=1). In response, system 100 provides the proper data value associated with this match (i.e., “PPP”) as the output data value, DATA.
In the foregoing manner, system 100 sequentially checks every entry in the chain until detecting a matching KEY value. The time required to process a KEY value will therefore vary, depending upon where a match is detected in the chain. Within system 100, the probability of two KEY values hashing to the same H_VALUE is initially about 1:220. This probability increases as the RAM routing table 110 is filled.
It would therefore be desirable to have an improved process for reducing the frequency of collisions in a system that hashes wide data values to narrow data values, thereby reducing the number of times that the wide data values must be processed using inefficient processing schemes, such as the one implemented by system 100. It would further be desirable if such an improved process can be implemented with relatively few additional hardware requirements.